The present invention relates to data compression of sampled physiological signals such as electrocardiogram signals; and, more particularly, to methods and apparatus for performing the data compression employing improved turning point methods.
ElectroCardioGram (ECG) monitoring systems such as Holter monitors are available to be worn externally by a patient to record electrical signals produced by the heart. Other ElectroGraM (EGM) monitors may be implanted within the body of a patient to record similar cardiac signals. Such monitoring systems are described in U.S. Pat. No. 5,312,446 and in U.S. Pat. No. 4,947,858, both of which are assigned to the assignee of the current invention, and are incorporated herein by reference.
Monitoring systems often have storage limitations. Cost, size, power consumption, and the sheer volume of data over time have limited external real-time Holter monitors to recording, at most, only twenty-four hour data segments. As an alternative, multiple shorter segments of data may be recorded when an irregular heartbeat is either automatically detected by the monitor, or is felt by the patient who then initiates the data storage.
Storage constraints are even more severe in implantable EGM monitoring systems, wherein conserving both power and space are prime considerations. Many different types of therapy delivery devices are associated with such monitoring systems including pacemakers, pacemaker/cardioverter/defibrillators, heart pumps, cardiomyostimulators, ischemia treatment devices, and drug delivery devices. Most of these cardiac systems include electrode pairs located adjacent to, or in, a heart chamber for sensing a xe2x80x9cnear-fieldxe2x80x9d EGM signals. Other systems have electrode pairs wherein both electrodes are implanted in the body with one of the electrodes being positioned at a predetermined distance from the heart and from the other electrode to perform sensing of xe2x80x9cfar-fieldxe2x80x9d EGM signals, which may also be called xe2x80x9csubcutaneous ECGxe2x80x9d signals. In either case, the near-field or far-field EGM signals are filtered and amplified for recording the sampled EGM, and for deriving event signals. Some of these Implantable Medical Devices (IMDs) are adapted to provide a therapy in response to the detection of these event signals. For example, the detection of a particular signal may initiate the delivery of a drug, a pacing signal, or another type of electrical stimulus to the patient.
Many IMDs store selected EGM signal segments and event data in internal RAM. This data may be transferred to an external programmer via a telemetry link. U.S. Pat. No. 5,312,446, referenced above, describes a system for storing such data on a First-In, First-Out (FIFO) basis. Another such system is provided by the Revea1(trademark) implantable loop recorder available from the MEDTRONIC(copyright) corporation. This device records a forty-two-minute segment of far-field EGM. When a patient detects an irregular heart beat, the patient uses a magnet to activate the device recording function so that the cardiac signals may be stored and later diagnosed by a clinician. The stored EGM data is periodically transmitted from device memory to an external programmer via a telemetry session.
Other types of physiological signals may also be stored by recording systems. Such signals include blood pressure signals associated with the heart chamber or adjoining blood vessels during the cardiac cycle. Blood temperature, blood pH, and a variety of blood gas-level indications may also be recorded. Recording systems for monitoring these types of signals are disclosed in commonly assigned U.S. Pat. Nos. 5,368,040, 5,535,752 and 5,564,434, and in U.S. Pat. No. 4,791,931, all incorporated by reference herein. The MEDTRONIC(copyright) Chronicle(copyright) implantable hemodynamic recorder employs the leads and circuitry disclosed in the above-incorporated, commonly assigned, ""752 and ""434 patents to record the EGM and absolute blood pressure values for certain intervals. The recorded data is periodically transferred to an external programmer via an uplink telemetry transmission.
As stated earlier, generally physiological signals of the type recorded by IMDs and external monitors are sensed by electrode pairs. The signals are then filtered, amplified, digitized, and stored in memory at a selected sampling frequency. The sampling frequency is selected based on the frequency components of the EGM or the ECG signal. Generally, a high enough sampling frequency is selected so that an accurate signal may be reconstructed and displayed later. At a sampling frequency of about 256 Hz, enough information is retained to accurately reconstruct visual displays of the ECG and EGM data. However, at this sampling rate, approximately twenty-two megabytes of storage space is required to record signal data over a twenty-four-hour period assuming each sample is stored as an 8-bit byte. At this rate, the storage requirements for even short EGM segments become prohibitive in IMDs given the inherent space and power constraints. Moreover, it would take up to five hours to transfer a twenty-four hour data segment employing current telemetry transmission techniques.
Because of these constraints, attempts have been made to lower sampling rates, and/or to compress the sampled data. Reducing the sampling rate from 256 Hz to 128 Hz significantly conserves available memory. In signals consisting of frequency components not greater than about 60 Hz, this sampling rate is adequate. However, some cardiac waveforms contain energy above 60 Hz. In these cases, the reduction in sampling rate results in loss of data. This may result in the loss of the slope and shape of the original waveform, making it difficult or impossible for the medical care providers to use the information to make a correct diagnosis.
Data compression techniques provide an alternative to merely reducing the sampling frequency. These techniques can be characterized as either xe2x80x9clossyxe2x80x9d or xe2x80x9closs-lessxe2x80x9d. When data is compressed using a xe2x80x9closs-lessxe2x80x9d method, it is possible to reconstruct the original waveform without losing information. Such non-distorting compression modes are exemplified by the Huffinan coding method and the Lempel-Ziv method, as described respectively in the following articles: Huffinan, D. A., xe2x80x9cA method for the construction of minimum-redundancy codesxe2x80x9d, Proc. IEEE, 40:1098-1101, 1952; and Ziv, J.; and Lempel, A., xe2x80x9cA universal algorithm for sequential data compression, IEEE Trans. Inform. Theory, IT-23, pp. 337-343, 1977.
Loss-less compression modes are computationally expensive, resulting in a more complex circuit design, increased power consumption, and a longer data processing time. These techniques may also require a considerable amount of memory to perform. Moreover, the compression rate that is achieved depends on the frequency content of the EGM and ECG signals. This frequency content will vary depending on the physiological condition being monitored. As a result, the amount of memory needed to store the compressed data cannot be determined in advance.
As an alternative to the use of a loss-less compression process, a lossy technique may be employed. Lossy techniques require less processing power to implement. The resulting system is therefore both smaller and more energy efficient. However, when data is compressed using a lossy method, some information is lost when the compressed data is used to re-construct the original waveform. For example, according to one approach, all xe2x80x9cbaselinexe2x80x9d sample values of a cardiac signal that occur between the PQRST waveform complexes are discarded. This can reduce memory requirements by about fifty percent for a normal sinus rhythm. In general, this is not acceptable, however, because many types of cardiac signals including Ventricular Tachycardia (VT), Ventricular Fibrillation (VF), Sinus Tachycardia (ST), and Atrial Fibrillation(AF) include virtually no baseline segments. These are the heart rhythms of greatest interest during the diagnosis of a cardiac abnormality.
More sophisticated, xe2x80x9clossyxe2x80x9d compression methods have been used for ECG storage in external devices. Examples of such techniques include the Amplitude-Zone-Epoch-Time-Coding (AZTEC) pre-processing software program. AZTEC is described in xe2x80x9cAZTEC, a pre-processing program for real-time ECG rhythm analysisxe2x80x9d by Cox, J. R. et al. (IEEE Trans. Biomed. Eng., BME-15, pp. 128-129.,1968.) The AZTEC algorithm has been used to store ECG data for automatic analysis functions such as QRS detection, but it has proven to be generally inadequate for a visual presentation of the data.
Another lossy technique is the SAPA, or xe2x80x9cfanxe2x80x9d method described in the above-incorporated ""858 patent, and is further discussed in xe2x80x9cScan-along polygonal approximation for data compression of electrocardiogramsxe2x80x9d, by Ishijima, M. et al. (IEEE Trans. Biomed. Eng., BME-26, pp. 723-729, 1983). This method uses a straight line approximation of the waveform to store the ECG data, and does not generally permit substantial data compression. This is because the error threshold is uniform over the entire input waveform. Therefore, the allowable error in the P-wave and T-wave regions limit the overall compression.
Yet another technique is referred to as the Coordinate-Reduction-Time-Encoding-System (CORTES). This mechanism may be used to achieve up to 10:1 data compression, as is described in xe2x80x9cData Compressionxe2x80x94Techniques and Applicationsxe2x80x9d, Pg. 256-259, T. J. Lynch. However, this technique is not considered adaptable for use in IMDs because of the processing power required to compress and store the data points in real time.
Other lossy data compression techniques are based upon domain transforms and include the Discrete Cosine Transform (DCT), the Walsh Transform, the Harr Wavelet Transform and the Daubechies Wavelet Transform. These techniques are relatively computationally intensive and are batch oriented. This means that these methods operate on a block of sequential data points at one time, and therefore are not easily implemented in integrated circuit hardware.
Another lossy compression mechanism is called the Mueller xe2x80x9cturning pointxe2x80x9d algorithm, as described by W. C. Mueller in xe2x80x9cArrhythmia detection program for an ambulatory ECG monitorxe2x80x9d (Biomed. Sci. Instrum. 14: 81-85, 1978). This algorithm achieves a fixed two-to-one compression ratio. The algorithm utilizes the last saved data point (X0) to determine which of the next two data points X1 or X2 to retain where X2 is the data point more recent in time. According to this algorithm, X1 will be retained if that data point is a xe2x80x9cturningxe2x80x9d point, meaning that the slope of the line between points X0 and X1 is positive whereas the slope of the line between X1 and X2 is negative, or vice versa. In other words. X1 is retained if it is a xe2x80x9cpeakxe2x80x9d or a xe2x80x9cvalleyxe2x80x9d in the waveform. Otherwise, X2 is retained.
The turning point algorithm is relatively simple to implement in either hardware, software, or a combination thereof. Moreover, even though the algorithm is lossy, the compressed data can, in many instances, be used to reconstruct a signal that retains the important peaks and valleys of a physiological signal. If greater than two-to-one compression is desired, the output of one turning point process may be cascaded with another compression iteration to achieve four-to-one compression.
Although the turning point mechanism provides many important advantages over other data compression schemes, in some instances, the turning point algorithm can discard important information. This occurs when both X1 and X2 are turning points, and X2 is a more important turning point than X1. For example, X1 and X2 may represent the Q and R waves of the QRS complex, respectively. The turning point algorithm will retain the smaller Q wave and discard the larger R wave. When the EGM or ECG trace is reconstructed from the compressed data, both the amplitude and the general shape of the resulting waveform is distorted. The effects are compounded when the turning point algorithm is cascaded to provide four-to-one data compression.
What is needed is an improved method and apparatus for data compression adaptable for use in an implantable medical device or external monitor having limited memory capacity. This method and apparatus should provide a sufficiently high compression factor, should not require large amounts of processing power to complete, and should provide reconstructed waveforms that are clinically acceptable.
It is therefore the primary object of the invention to provide an improved data compression system and method;
It is another object of the invention to provide an improved data compression system and method that provides two-to-one data compression;
It is still another object of the invention to provide an improved data compression system and method that can be cascaded to provide increased data compression ratios;
It is a yet another object of the invention to provide a turning point method that retains the optimal turning point in a frame containing N data points;
It is a further object of the invention to provide a system using an improved turning point process to compress EGM data within an implantable medical device;
It is a further object of the invention to provide a system using an improved turning point method to compress data derived from physiologic sensors in an implantable medical device;
It is still another object of the invention to provide improved data compression capabilities without increasing power consumption;
It is yet another object of the invention to provide improved data compression capabilities without substantially increasing processing requirements;
It is still another object of the invention to provide an improved turning point system and method that uses the xe2x80x9clargest unshared legxe2x80x9d of an input waveform to select a data sample to retain from among a predetermined number of consecutive turning points;
It is another object of the invention to provide an improved turning point system and method that uses the xe2x80x9clargest peakxe2x80x9d of an input waveform to select a data sample to retain from among a predetermined number of consecutive turning points;
It is still another object of the invention to provide an improved turning point system and method that uses a xe2x80x9cgreatest difference from X0xe2x80x9d to select a data sample to retain from among a predetermined number of consecutive turning points;
It is another object of the invention to provide an improved turning point system and method that uses xe2x80x9ca largest positive peakxe2x80x9d of an input waveform to select a data sample to retain from among a predetermined number of consecutive turning points;
It is yet a further object of the invention to provide an improved turning point system and method that uses xe2x80x9ca least positive peakxe2x80x9d of an input waveform to select a data sample to retain from among a predetermined number of consecutive turning points;
It is another object of the invention to provide an improved turning point system and method having selectable criterion for selecting a first predetermined number of turning points to retain from among a second predetermined number of consecutive turning points;
It is yet another object of the invention to provide an improved turning point system and method having a variable compression ratio depending on the frequency of the sampled input waveform;
It is yet a further object of the invention to provide a method for calculating the distance between consecutive, retained data samples for use in constructing the sampled waveform;
It is a further object of the invention to provide a method for calculating the distance between consecutive, retained data samples for use in constructing the sampled waveform, wherein the distance between consecutive, retained data samples is calculated to describes a sample frequency that is less than the frequency of the input waveform;
It is yet another object of the invention to provide a method for compressing data samples that includes an amplitude companding mechanism; and
It is another object to provide a system and method that can provide improved data compression capabilities while being implemented in hardware, software, or a combination thereof.
Other objects of the inventive system and method are described in the following specification and claims.
These and other objects of the present invention are realized in improved turning point system and method for performing data compression. The system improves the conventional turning point compression method by selecting a predetermined number of the xe2x80x9cbestxe2x80x9d turning points included in the sample window framed by data samples X0 and XN, wherein the framed data samples include X1, X2 . . . X(N-1). From this sample window, ones of the data samples X1 through X(N-1) will be identified as turning points using a selected one of the turning point detection methods discussed below. Using the turning point detection information, a predetermined number of samples are selected for retention. These samples may represent the best turning points based on a first predetermined set of criteria. If no turning points are detected, these samples are selected using a second predetermined set of criteria. The samples selected for retention are then stored. After selection of the retained samples, X0 is set to the value of the most recently-retained data sample, X1 is set to the value of XN, and the process is repeated.
As noted above, several mechanisms may be use to determine which data samples are considered turning points. In one embodiment, a data sample is considered to be a turning point if the slopes of the two lines interconnecting that data sample with the two adjacent data samples change polarity. For example, if the line interconnecting X0 and X1 has a positive slope, whereas the line interconnecting X1 and X2 has a negative slope (or vice versa), X1 is considered a turning point. Thus, in this instance, a turning point represents a peak or a valley in a waveform. In an alternative embodiment, a turning point may also include those points wherein a line having a non-zero slope intersects with a line having a zero slope. These turning points represent points wherein a xe2x80x9cplateauxe2x80x9d in a waveform meets a rising or falling portion of a waveform.
In yet a third embodiment, a turning point is defined as a point at which the waveform transitions from a generally xe2x80x9cuphillxe2x80x9d topology to a generally xe2x80x9cdownhillxe2x80x9d topology, or vice versa. For example, consider a data sample window framed by data points X0 through XN with XM being a data point somewhere between data points X0 through XN Assume that the slopes of the lines drawn between consecutive pairs of data points between X0 through XM are all either positive or zero. This waveform segment between points X0 and XM therefore represents a generally upward trend in the waveform. At XM, the waveform takes a downward turn, such that the slope of the line between data points XM and the next consecutive data point X(M+1) is negative. Since this negative, non-zero slope has a different polarity then the last non-zero slope that was encountered, XM is considered a turning point.
According to one mechanism, amplitude thresholding is used to determine whether a detected turning point should be retained. If the difference between the amplitudes of consecutive data points XM and X(M+1) is less than a predetermined threshold value, then X(M+1) may be eliminated as a turning point even if that point meets other pre-selected criteria. This mechanism removes from consideration small-amplitude turning points that are likely the result of noise. In one embodiment, the threshold value may be programmable so that turning point retention may be adapted to the noise level.
Once all turning points are identified within sample window X0 through XN, the current invention selects the xe2x80x9cbestxe2x80x9d of these turning points for retention. Several selection mechanisms are available for selecting the xe2x80x9cbestxe2x80x9d turning points. According to one embodiment of the invention, the sample window includes data samples X0 through X3, and the best turning point is determined by measuring which of the xe2x80x9cunshared legsxe2x80x9d of the waveform segment being considered is the largest. The unshared legs include a first line interconnecting X0 and X1, and a second line interconnecting X2 and X3. As between X1 and X2, the data point that is included within the segment having the largest change in amplitude is retained. It may be noted that this embodiment may retain a first data point over a second data point even in some situations in which the second data point is associated with a higher amplitude than the first data point. This is so because this criterion is not based upon absolute amplitude, but rather the size of the change between adjacent data points. In general, this criterion will reliably select the R wave of a PQRST complex within an EGM waveform, and therefore provides better compression as compared to the prior art turning point mechanisms.
A second embodiment of the invention selects the xe2x80x9cbestxe2x80x9d turning point by determining which of the turning points within the window X0 through XN has the greatest signal amplitude compared to a reference value, which in the preferred embodiment is zero volts. Unlike the xe2x80x9clargest unshared legxe2x80x9d mechanism of the foregoing paragraph, the best turning point in this instance is considered to be the turn having the greatest absolute amplitude, regardless of the size of the turn. Yet another embodiment selects as the best turning point that point which has an amplitude that differs the most from the amplitude of X0. Still another embodiment retains the turning point that is more positive than the other. This may be used to process signals in which the higher-amplitude segments are of more interest than the low-amplitude signals. Another embodiment retains the one of two turning points that is less positive than the other, and may be employed to process signals in which the low-amplitude or negative segments are of the highest interest. In one embodiment of the invention, the selection criterion is programmably-selectable based on the data set being processed.
It may be noted that more than one turning point may be retained per sample window. In this instance, many combinations of criteria may be devised to select the points to retain. For example, assuming two points are to be retained per frame, the two most positive peaks may be retained. Alternatively, the largest positive peak and the largest negative peak may be retained. In yet another embodiment, a largest positive peak value and the point representing the largest difference from X0 may be retained. Many different combinations may be defined, and any number P data samples may be retained wherein P is less than N. This provides a compression ratio of (Nxe2x88x921)-to-P when a sample window of N+1 data samples is used.
In some embodiments, the compression ratio may be variable. This allows a variable number of data samples within a given sample window to be retained depending on the number of turning points detected within the window. For example, if the frequency of the input signal is high such that a relatively large number of the data samples within the sample window are turning points, a larger-than-average number of data samples may be retained for that sample window. A smaller-than-average number of data samples may be stored during another sample window. This may occur, for example, in a window in which no turning points are detected. Since it is desirable to have the average number of samples retained per sample window approach some predetermined target average value, a count of the number of xe2x80x9cexcessxe2x80x9d data points that have been retained as compared to the target average is maintained. When this excess count exceeds a predetermined threshold value, the number of data points that may be retained during subsequent sample windows is temporarily reduced until the average number of saved data points per frame once again approximates the predetermined target average.
In embodiments in which the compression ratio varies depending on the input frequency, it may be desirable to save position data. This position data indicates the distance between consecutive data points such that waveform re-construction can be performed in a more accurate manner. This position data may precisely indicate the distance between retained data points. Alternatively, the position data may give an approximate distance between two points. For example, in one implementation, the position data indicates how many one-half sample windows exist between two retained sample points. According to this implementation, the position data only provides information at one-half of the input frequency of the sample data, such that some data is lost during this calculation. As a result, waveform re-construction cannot be performed with one hundred percent accuracy. However, this mechanism has the advantage of providing compacted position data that consumes less memory space.
In one implementation of the invention, position data may be stored in the same addressable storage location as a respective one of the retained sample. Alternatively, this position data may be stored in a different addressable storage location.
Another aspect of the invention relates to amplitude companding. The amplitudes of retained data samples may be scaled by a predetermined scaling factor so that less memory is required to store the samples. For example, an eight-bit digital data sample may be companded to six bits by dividing the data sample value by a factor of four. In another implementation, different scaling factors are used depending on the amplitude of the sample. High-amplitude and low-amplitude samples may be scaled more than mid-range signals, which are of interest when detecting the P-waves of an EGM signal, for example. Amplitude companding may be useful when position data is to be stored within a retained data sample. For example, an eight-bit data sample may be companded to six bits and stored in the same addressable memory byte with a respective two-bit position indicator. Other combinations of position data and signal data are, of course, possible.
The current turning point system and method may be cascaded to provide additional data compression. This cascading may be performed either serially or in parallel. For example, a two-to-one compression method may be applied to a data set twice to achieve four-to-one compression. Applying the method once again to the data set achieves eight-to-one data compression, and so on.